To receive messages from other computing devices, a computing device establishes a connection to one of many connection servers. After establishing a connection to a connection server, any message intended for that computing device must be routed through the connection server to which the computing device is connected. Accordingly, the connection server propagates this device-to-connection server mapping data globally such that, upon receipt of a message intended for the device, messaging servers can determine the appropriate connection server to send the message. When the computing device loses its connection to the connection server, it must reestablish its connection or connect to a different connection server. After reestablishing a connection or establishing a new connection, there is a blackout period during which the device-to-connection server mapping data is globally propagated, which causes a blackout period during which the device is incapable of receiving messages.